package 子数组问题;

/**
 * @Date 2024/5/31 9:37
 * @description: 力扣53: 最大子数组和(子数组是连续的)
 * .            https://leetcode.cn/problems/maximum-subarray/description/
 * @Author LittleNight
 */
public class likou53 {

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] f = new int[n]; // 表示以 i 位置为结尾的所有子数组的最大和
        f[0] = Math.max(nums[0], 0);

        for (int i = 1; i < n; i++) {
            // f[i] = f[i - 1] + nums[i];
            f[i] = Math.max(f[i - 1] + nums[i], nums[i]);
        }
        // 遍历 f 表, 求出一个最大值
        int ret = 0;
        for (int i = 0; i < n; i++) {
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }
}
